/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution331 {

    public static void main(String args[]) {
        Solution331 s = new Solution331();
        System.out.println(s.isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#,#"));
    }

    public boolean isValidSerialization(String preorder) {
        String[] ws = preorder.split(",");
        char[] stack = new char[ws.length];
        int top = -1;

        for (int i = 0; i < ws.length; i++) {
            char c = ws[i].charAt(0);
            stack[++top] = c;
            int idx = top;
            while (idx >= 2 && stack[idx] == '#' && stack[idx - 1] == '#' && stack[idx - 2] != '#') {
                stack[idx - 2] = '#';
                idx -= 2;
            }
            top = idx;
        }
        if(top == 0 && stack[0] == '#'){
            return true;
        }
        return false;
    }
}
